/******************************************************************************
* 文件名称: memory.c
* 内容摘要: 内存管理
* 创建者の: 孔佳伟
* 个人主页: https://gitee.com/thin-wind/jump
* 修改记录: 
******************************************************************************/

#include <memory.h>
#include <list.h>


/************************* fixed memory start ********************************/

// FM -- fixed memory: 定长内存

// 定长内存分配单元长度
#define FM_ALLOC_SIZE       32
#define FM_NODE_SIZE        sizeof(FM_NODE)

// 定长内存分配单元
typedef U08 (FM_UNIT)[FM_ALLOC_SIZE];

typedef union _FM_NODE    FM_NODE;

// 定长内存管理单元，使用 union 是为了尽量少的使用内存，其实应该使用 struct 
union _FM_NODE
{
    FM_NODE*        next;           // 指向下一个节点
    FM_UNIT*        unit;           // 指向分配单元
};

// 定长内存管理链表头类型
typedef struct FM_LIST
{
    FM_NODE*        node;           // 管理单元节点
    FM_NODE*        nbase;          // 管理单元基址
    FM_UNIT*        ubase;          // 分配单元基址
    U32             max;            // 最多可分配的空闲单元个数
} FM_LIST;

static FM_LIST  FM_LIST_HEAD;              // 定长内存管理链表头

/******************************************************************************
* 函数名称: static E_RET FixedMemInit(U08* mem, U32 size)
* 功能说明: 定长内存管理初始化
* 输入参数: U08* mem        --定长内存基址
    　　　　U32 size        --定长内存长度
* 输出参数: 无
* 函数返回: E_OK:成功; E_ERR:失败
* 其它说明: 以管理单元为节点，将管理单元组织成单向链表
******************************************************************************/
static E_RET FixedMemInit(U08* mem, U32 size)
{
    U32 max = 0;
    U32 i = 0;
    FM_NODE* current = NULL;    // 当前管理单元节点
    FM_NODE* next = NULL;       // 下一个管理单元节点

    // 检查参数合法性
    if(NULL == mem || size < (FM_NODE_SIZE + FM_ALLOC_SIZE))
        return E_ERR;

    // 计算一块内存最多可以分成多少个内存单元（1内存单元 = 1管理单元+1分配单元）
    max = size / (FM_NODE_SIZE + FM_ALLOC_SIZE);
    
    // 初始化定长内存链表，以管理单元为节点，将所有的管理单元组织成一个单向链表
    FM_LIST_HEAD.max    = max;
    FM_LIST_HEAD.nbase  = (FM_NODE *)mem;                               // 管理单元基址
    FM_LIST_HEAD.ubase  = (FM_UNIT *)((U32)mem + max*FM_NODE_SIZE);     // 分配单元基址
    FM_LIST_HEAD.node   = (FM_NODE *)mem;
    for(i = 0; i < max - 1; i++)
    {
        // 当前节点（管理单元）的 next 指针指向下一个节点（管理单元）
        current = FM_LIST_HEAD.node + i;
        next = FM_LIST_HEAD.node + i + 1;
        current->next = next;
    }

    // 最后一个节点（管理单元）的 next 指针指向 NULL
    next->next = NULL;

    return E_OK;
}

/******************************************************************************
* 函数名称: static void* FixedMemAlloc(void)
* 功能说明: 定长内存申请
* 输入参数: 无
* 输出参数: 无
* 函数返回: void*           --申请到的分配单元地址
* 其它说明: FM_LIST_HEAD 链表中所有节点都是可用的
           申请时只要将第一个节点所对应的分配内存地址返回，并将该节点从链表中删除即可
******************************************************************************/
static void* FixedMemAlloc(void)
{
    void* alloc = NULL;
    FM_NODE* node = NULL;
    U32 index = 0;

    // 如果头结点为空，表明已经没有空闲的内存可分配了
    if(NULL == FM_LIST_HEAD.node)
        return NULL;
    
    // 取空闲定长内存管理单元链表第一个节点
    node = FM_LIST_HEAD.node;
    
    // 计算出是第几个管理单元，其在管理单元中的偏移个数就等同于在分配单元中的偏移个数
    // 根据这个偏移量就能算出对应的分配单元地址，最后再将这个分配单元地址返回
    index = (U32)(node - FM_LIST_HEAD.nbase);
    alloc = FM_LIST_HEAD.ubase + index;

    // 从链表头删除节点，即将 FM_LIST_HEAD 的头结点指向下一个节点
    FM_LIST_HEAD.node = node->next;

    // 用于释放内存时校验
    node->unit = alloc;

    return alloc;
}

/******************************************************************************
* 函数名称: static E_RET FixedMemFree(void* ptr)
* 功能说明: 定长内存释放
* 输入参数: void* ptr       --要释放的分配单元地址
* 输出参数: 无
* 函数返回: E_OK:成功; E_ERR:失败
* 其它说明: 根据传入的分配单元地址 ptr，计算出对应的管理单元，将其加入到 FM_LIST_HEAD 链表中
******************************************************************************/
static E_RET FixedMemFree(void* ptr)
{
    U32 index = 0;
    FM_NODE* node = NULL;

    // 检查参数合法性
    if(NULL == ptr)
        return E_ERR;

    // 计算出是第几个分配单元，其在分配单元中的偏移个数就等同于在管理单元中的偏移个数
    // 根据这个偏移值就能算出对应的管理单元地址，最后再将这个管理单元插入链表头
    index = (U32)((FM_UNIT *)ptr - FM_LIST_HEAD.ubase);
    // 合法性检查
    if(index >= FM_LIST_HEAD.max)
        return E_ERR;
    node = FM_LIST_HEAD.nbase + index;
    // node->unit 在 FixedMemAlloc 被赋值，只有当申请内存地址与释放内存地址相同是才合法
    if(node->unit != ptr)
        return E_ERR;

    // 将节点插入链表头
    node->next = FM_LIST_HEAD.node;
    FM_LIST_HEAD.node = node;

    return E_OK;
}
/*************************** fixed memory end ********************************/

/************************* volatile memory start *****************************/

// VM -- volatile memory: 变长内存

// 变长内存管理头类型
typedef struct VM_HEAD
{
    LIST_NODE       node;               // 链表节点
    U32             usedSize;           // 已分配内存空间大小
    U32             freeSize;           // 空闲内存空间大小
} VM_HEAD;

#define VM_HEAD_SIZE        sizeof(VM_HEAD)

static LIST     VM_LIST;                   // 变长内存管理链表


/******************************************************************************
* 函数名称: static E_RET VolatileMemInit(U08* mem, U32 size)
* 功能说明: 变长内存管理初始化
* 输入参数: U08* mem        --变长内存基址
    　　　　U32 size        --变长内存长度
* 输出参数: 无
* 函数返回: E_OK:成功; E_ERR:失败
* 其它说明: 
******************************************************************************/
static E_RET VolatileMemInit(U08* mem, U32 size)
{
    VM_HEAD* head = (VM_HEAD *)mem;
    
    // 检查参数合法性
    if(NULL == mem || size < VM_HEAD_SIZE)
        return E_ERR;

    // 初始化变长内存管理链表
    ListInit(&VM_LIST);
    // 初始化第一个节点的管理头
    head->usedSize = 0;                      // 初始化时已分配的内存大小为 0
    head->freeSize = size - VM_HEAD_SIZE;    // 空闲区域大小要除去管理头本身所占的内存空间
    // 将第一个节点插入链表 VM_LIST 末尾
    ListAddTail(&VM_LIST, (LIST_NODE *)head);

    return E_OK;
}

/******************************************************************************
* 函数名称: static void* VolatileMemAlloc(U32 size)
* 功能说明: 变长内存申请
* 输入参数: U32 size        --要申请的内存大小
* 输出参数: 无
* 函数返回: void*           --申请到的内存首地址
* 其它说明: 
******************************************************************************/
static void* VolatileMemAlloc(U32 size)
{
    LIST_NODE* pListNode = NULL;
    VM_HEAD* head = NULL;
    VM_HEAD* newHead = NULL;
    U32 allocSize = size + VM_HEAD_SIZE; // 申请内存的总大小要包含管理头本身所占的内存空间

    // 遍历 VM_LIST
    LIST_FOR_EACH(&VM_LIST, pListNode)
    {
        head = (VM_HEAD *)LIST_NODE(pListNode, VM_HEAD, node);
        // 找到空闲内存且空闲内存大小要足够分配
        if(head->freeSize >= allocSize)
        {
            // 原空闲内存的后面分配出 allocSize 大小的内存
            // 新的管理头指针指向分配出的新内存首地址
            newHead = (VM_HEAD *)((U32)head + VM_HEAD_SIZE + head->usedSize + head->freeSize - allocSize);
            newHead->usedSize = size;       // 已分配内存大小
            newHead->freeSize = 0;          // 空闲内存大小
            head->freeSize -= allocSize;    // 减掉分配出去的内存大小  
            ListAddAfter((LIST_NODE *)head, (LIST_NODE *)newHead);      // 新节点 newHead 插入到 head 节点后面 
            break;
        }
    }

    // 判断 newHead 是否为 NULL，若为 NULL，则表明未找到可分配的内存，返回 NULL 
    // 如果 newHead 不为 NULL，则表明已成功分配到内存空间，返回实际空闲可用内存的首地址
    return newHead ? (void *)((U32)newHead + VM_HEAD_SIZE) : NULL;
}

/******************************************************************************
* 函数名称: static E_RET VolatileMemFree(void* ptr)
* 功能说明: 变长内存释放
* 输入参数: void* ptr       --要释放的内存首地址
* 输出参数: 无
* 函数返回: E_OK:成功; E_ERR:失败
* 其它说明: 
******************************************************************************/
static E_RET VolatileMemFree(void* ptr)
{
    LIST_NODE* pListNode = NULL;
    VM_HEAD* head = NULL;
    VM_HEAD* prev = NULL;

    // 检查参数合法性
    if(NULL == ptr)
        return E_ERR;

    // 遍历 VM_LIST
    LIST_FOR_EACH(&VM_LIST, pListNode)
    {
        head = (VM_HEAD *)LIST_NODE(pListNode, VM_HEAD, node);
        // 传入地址 ptr 与要释放的内存首地址相同时才能释放内存
        if((U32)head + VM_HEAD_SIZE == (U32)ptr)
        {
            prev = (VM_HEAD *)(head->node.prev);
            prev->freeSize = prev->freeSize +  head->usedSize + VM_HEAD_SIZE;
            ListDelNode(pListNode); // 删除链表节点
            return E_OK;
        }
    }
    return E_ERR;
}

/************************** volatile memory end ******************************/

/******************************************************************************
* 函数名称: E_RET MemInit(U08* mem, U32 size)
* 功能说明: 内存管理初始化
* 输入参数: U08* mem        --内存基址
    　　　　U32 size        --内存长度
* 输出参数: 无
* 函数返回: E_OK:成功; E_ERR:失败
* 其它说明: 将传入的 mem 内存区分两半，前半部分用定长内存管理法，后半部分用变长内存管理法 
******************************************************************************/
E_RET MemInit(U08* mem, U32 size)
{
    E_RET ret = E_ERR;

    U08* fmem    = mem;
    U32  fsize   = size / 2;
    U08* vmem    = (U08 *)((U32)fmem + fsize);
    U32  vsize   = size - fsize;
    
    ret = FixedMemInit(fmem, fsize);
    ret &= VolatileMemInit(vmem, vsize);

    return ret;
}

/******************************************************************************
* 函数名称: void* Malloc(U32 size)
* 功能说明: 内存申请
* 输入参数: U32 size        --要申请的内存大小
* 输出参数: 无
* 函数返回: void*           --申请到的内存首地址
* 其它说明: 判断申请内存大小是否大于 32 字节，若不大于 32 字节，则使用定长内存申请，
           若大于 32 字节，则使用变长内存申请
******************************************************************************/
void* Malloc(U32 size)
{
    void* ret = NULL;

    if(size > FM_ALLOC_SIZE)
        ret = VolatileMemAlloc(size);
    else
    {
        ret = FixedMemAlloc();
        if(NULL == ret) // 如果定长内存申请失败，则再尝试变长内存申请
            ret = VolatileMemAlloc(size);
    }
        
    return ret;
}

/******************************************************************************
* 函数名称: Free(void* ptr)
* 功能说明: 内存释放
* 输入参数: void* ptr       --要释放的内存首地址
* 输出参数: 无
* 函数返回: E_OK:成功; E_ERR:失败
* 其它说明: 先尝试定长内存释放，定长内存释放不成功再尝试变长内存释放
******************************************************************************/
E_RET Free(void* ptr)
{
    if(E_ERR == FixedMemFree(ptr))
        return VolatileMemFree(ptr); 
    return E_OK;
}

